package 数据结构设计高频题;


import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 插入、删除和获取随机元素O(1)时间的结构
// 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/
public class Code03_InsertDeleteRandom {

    class RandomizedSet {
        public HashMap<Integer, Integer> val_IndexMap;
        public ArrayList<Integer> arr;
        public RandomizedSet() {
            val_IndexMap = new HashMap<>();
            arr = new ArrayList<>();
        }

        public boolean insert(int val) {
            if(val_IndexMap.containsKey(val)){
                return false;
            }
            val_IndexMap.put(val, arr.size());
            arr.add(val);
            return true;
        }

        public boolean remove(int val) {
            if(!val_IndexMap.containsKey((val))){
                return false;
            }
            int remove_Index = val_IndexMap.get(val);
            int move_Value = arr.get(arr.size() - 1);
            arr.set(remove_Index, move_Value);
            arr.remove(arr.size() - 1);
            val_IndexMap.replace(move_Value, remove_Index);
            val_IndexMap.remove(val);
            return true;
        }

        public int getRandom() {
            return arr.get((int) (Math.random() * arr.size()));
        }
    }
}
